package exercises;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-09
 * Time: 19:49
 */

/**
 *
 代码
 测试用例
 笔记
 笔记
 测试结果
 测试结果
 面试题 02.02. 返回倒数第 k 个节点
 简单
 相关标签
 相关企业
 提示
 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

 注意：本题相对原题稍作改动

 示例：

 输入： 1->2->3->4->5 和 k = 2
 输出： 4
 说明：

 给定的 k 保证是有效的
 */
public class Exercises3 {

    static class ListNode{
        public int val;
        public ListNode next;
    }

    public int kthToLast(ListNode head, int k) {
        if(head == null) {
            return -1;
        }

        ListNode fast = head;
        ListNode slow = head;
        int count = 0;

        //fast先走K-1步
        while(count != k-1) {
            //不计算链表长度情况下；不能让fast走超出链表，导致空指针异常
            if(fast == null) {
                return -1;
            }

            fast = fast.next;
            count++;
        }

        //两个指针一起走
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow.val;
    }
}
